package sort;

import java.util.ArrayList;
import java.util.List;

/**
 * Given a collection of intervals, merge all overlapping intervals
 * <p>
 * Input: [[1,3],[2,6],[8,10],[15,18]]
 * Output: [[1,6],[8,10],[15,18]]
 * Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
 * <p>
 * <p>
 * Input: [[1,4],[4,5]]
 * Output: [[1,5]]
 * Explanation: Intervals [1,4] and [4,5] are considered overlapping.
 */
public class mergeIntervals {
    public void solution(twoNodeMode[] array) {
        baseSort4QuickSort sort = new baseSort4QuickSort();
        sort.quickSort(array, 0, array.length - 1);
        int i = 0;
        List<twoNodeMode> list = new ArrayList();
        for (twoNodeMode node : array) {
            list.add(node);
        }
        for (int j = 1; j < list.size(); j++) {
            if (list.get(j).start > list.get(i).end) {
                i++;
            } else {
                list.get(i).end = Math.max(list.get(i).end, list.get(j).end);
                list.remove(list.get(j));
                j--;
            }
        }
        for (twoNodeMode node:list){
            System.out.println(node.start+":"+node.end);
        }

    }

    public static void main(String[] args) {
        twoNodeMode[] array = {new twoNodeMode(1, 3), new twoNodeMode(2, 4), new twoNodeMode(3, 5),
                new twoNodeMode(2, 6), new twoNodeMode(4, 9)};
        mergeIntervals merge = new mergeIntervals();
        merge.solution(array);
    }

}
